//There are a total of numCourses courses you have to take, labeled from 0 to 
//numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai,
// bi] indicates that you must take course bi first if you want to take course ai.
// 
//
// 
// For example, the pair [0, 1], indicates that to take course 0 you have to 
//first take course 1. 
// 
//
// Return true if you can finish all courses. Otherwise, return false. 
//
// 
// Example 1: 
//
// 
//Input: numCourses = 2, prerequisites = [[1,0]]
//Output: true
//Explanation: There are a total of 2 courses to take. 
//To take course 1 you should have finished course 0. So it is possible.
// 
//
// Example 2: 
//
// 
//Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
//Output: false
//Explanation: There are a total of 2 courses to take. 
//To take course 1 you should have finished course 0, and to take course 0 you 
//should also have finished course 1. So it is impossible.
// 
//
// 
// Constraints: 
//
// 
// 1 <= numCourses <= 10⁵ 
// 0 <= prerequisites.length <= 5000 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// All the pairs prerequisites[i] are unique. 
// 
// Related Topics Depth-First Search Breadth-First Search Graph Topological 
//Sort 👍 7300 👎 295


package leetcode.editor.en;

import java.util.ArrayList;
import java.util.List;

public class _207_CourseSchedule {
    public static void main(String[] args) {
        Solution solution = new _207_CourseSchedule().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<List<Integer>> adapt = new ArrayList<>(numCourses);
            for (int i = 0; i < numCourses; i++) {
                adapt.add(new ArrayList<>());
            }
            for (int[] prerequisite : prerequisites) {
                adapt.get(prerequisite[1]).add(prerequisite[0]);
            }
            int[] flags = new int[numCourses];
            for (int i = 0; i < numCourses; i++) {
                if(!dfs(adapt, flags, i)){
                    return false;
                }
            }
            return true;
        }

        private boolean dfs(List<List<Integer>> adapt, int[] flags, int i) {
            if (flags[i] == 1) {
                return false;
            }
            if (flags[i]==-1) {
                return true;
            }
            flags[i] = 1;
            List<Integer> integers = adapt.get(i);
            for (Integer integer : integers) {
                if(!dfs(adapt, flags, integer)) {
                    return false;
                }
            }
            flags[i] = -1;
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}